home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 7347 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.8 KB  |  99 lines
  1. Path: camelot.dsccc.com!not-for-mail
  2. From: kcline@sun152.spd.dsccc.com (Kevin Cline)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 22 Feb 1996 14:41:54 -0600
  6. Organization: DSC Communications Corporation Switch Products Division
  7. Message-ID: <4gikei$nh7@sun152.spd.dsccc.com>
  8. References: <4fr8be$ass@news.iconn.net> <danpop.824595562@rscernix> <4gaucn$cdu@beyond.escape.com> <4gh4cq$8eo@agate.berkeley.edu>
  9. NNTP-Posting-Host: sun152.spd.dsccc.com
  10.  
  11. In article <4gh4cq$8eo@agate.berkeley.edu>,
  12. Bruce Kaskel <kaskel@durban.berkeley.edu> wrote:
  13. >...
  14.  
  15. This thread should be dead.  Here is a tested program so simple and fast 
  16. (about as fast as converting a number to base 5) that I can
  17. compute the last digit of any factorial up to about 10000
  18. in my head, and can also compute the last digit of factorials of large
  19. powers of 10 (like 1 billion) in my head.
  20.  
  21.     #include <iostream.h>
  22.     #include <stdlib.h>
  23.  
  24.     // last digits of powers of two
  25.     static int t0[] = { 6, 2, 4, 8 };
  26.  
  27.     // powers of two (mod 5) of 0! - 4!
  28.     static int t1[] = { 0, 0, 1, 0, 2 } ;
  29.  
  30.     static int f(int i) {
  31.       if (i == 0) return 0;
  32.       return t1[i % 5] + i/5 + f(i/5);
  33.     }
  34.  
  35.     static int lastNonZeroDigitOfFactorial(int i) {
  36.       if (i < 2) return 1;
  37.       return t0[f(i) % 4];
  38.     }
  39.  
  40.     int main(int argc, char **argv) {
  41.       if (argc < 2) {
  42.     cout << "usage: " << argv[0] << " n\n";
  43.     exit(1);
  44.       }
  45.  
  46.       int i = atoi(argv[1]);
  47.       if (i < 0) {
  48.     cout << argv[0] << ": non-negative argument required\n";
  49.     exit(1);
  50.       }
  51.  
  52.       cout << "The last non-zero digit of " << i << "! is "
  53.        << lastNonZeroDigitOfFactorial(i) << endl;
  54.     }  
  55.  
  56. To compute this in your head, just keep dividing by 5, adding the
  57. quotients + 1 when the remainder is 2 and 2 when the remainder is 4,
  58. and continually reducing mod 4.
  59.  
  60. Computing the last non-zero digit of 1000000!:
  61.  
  62. f(1000000) = f(200000) (mod 4)    (No remainder when divided by 4 or 5)
  63. f(200000) = f(40000) (mod 4)
  64. f(40000) = f(8000) (mod 4)
  65. f(8000) = f(1600) (mod 4)
  66. f(1600) = f(320) (mod 4)
  67. f(320) = f(64) (mod 4)
  68. f(64) = 2 + 2 + f(12) = f(12) (mod 4)
  69. f(12) = 1 + 2 + f(2) = 3 + 2 + f(2) (mod 4) = 1 + 1 = 2 (mod 4)
  70.  
  71. The last non-zero digit in 1000000! is t0[2] (2**2) or 4.
  72.  
  73. Now we see that the last non-zero digit in 10**n is the same
  74. as the last non-zero digit in 2**n, so to compute 
  75. the last non-zero digit in 1000000000!
  76.  
  77. f(1000000000) = f(512)
  78. f(512) = t1[2] + 102 + f(102)
  79.        =   1   +  2  + t1[2] + 20 + f(20)
  80.        =   3         +   1   + 4 + f(4)
  81.        =   0 + t1[4]
  82.        = 2
  83.  
  84. The last digit of 1000000000! is t0[2] or 4.   
  85.  
  86. It's a bit harder for non-powers of 10, like 9731!
  87.  
  88. f(9731) = 1946 + f(1946)
  89.     = 2 + 389 + f(389)
  90.     = 3 +       2 + 77 + f(77)
  91.     = 2 + 15 + f(15)    
  92.     = 1 + f(3) 
  93.         = 1
  94.  
  95. The last non-zero digit of 9731! is t0[1] (2**1) or 2.
  96.  
  97. -- 
  98. Kevin Cline
  99.